import java.util.Arrays;

class BinarySearch {
    public static void main(String[] args) {
        int[] nums = {1,2,3,5,8,12,12,12,34,36,36,47};
        int key = 12;
//        System.out.println(binarySearch(nums,key));
//        System.out.println(binarySearchFirstBiggerNum(nums,key));
        System.out.println(binarySearchLeftFirst(nums, 36));
    }

    /**
     * 双指针法解决问题
     * lp指向下界，rp指向上界；每次/2，上界，下界分别与搜索值进行比较
     */
    /**
     * @param nums
     * @return
     */
    private static int binarySearch(int[] nums,int key) {
        int lp = 0;
        int rp = nums.length-1;
        int result = -1;
        while(lp <= rp){
            int mid = (lp + rp)/2;
            if(nums[mid] > key){
                rp = mid -1;
            } else if (nums[mid] < key) {
                lp = mid +1;
            }else {
                return mid;
            }
        }
        return result;
    }

    private static int binarySearch(int[] nums,int key,int start,int end) {
        int lp = 0;
        int rp = nums.length-1;
        int result = -1;
        while(lp <= rp){
            int mid = (lp + rp)/2;
            if(nums[mid] > key){
                rp = mid -1;
            } else if (nums[mid] < key) {
                lp = mid +1;
            }else {
                return mid;
            }
        }
        return result;
    }

    private static int binarySearchFirstBiggerNum(int[] nums,int key) {
        int lp = 0;
        int rp = nums.length-1;
        int bigNum = -1;
        while(lp <= rp){
            int mid = (lp + rp)/2;
            if(nums[mid] > key){
                bigNum = nums[mid];
                rp = mid -1;
            } else if (nums[mid] <= key) {
                lp = mid +1;
            }
        }
        return bigNum;
    }


    private static int binarySearchLeftFirst(int[] nums,int key) {
        int lp = 0;
        int rp = nums.length-1;
        int temp =-1;
        while(lp <= rp){
            int mid = (lp + rp)/2;
            if(nums[mid] > key ){
                rp = mid -1;
            } else if (nums[mid] < key) {
                lp = mid +1;
            }else {
                temp = mid;
                rp = mid -1;
            }
        }
        return temp;
    }
}